#pragma once

#include <string>
#include <vector>

namespace regex
{
    
enum Anchor 
{
    kNone  = 0x00,
    kBegin = 0x01,
    kEnd   = 0x02,
};

struct Input
{
    Input(const std::string &str, uint index)
        : m_string(str), m_index(index)
    {
        m_epsilon = index >= str.size();
    }

    bool is_epsilon() const
    {
        return m_string.empty() || m_epsilon;
    }
    
    Input epsilon() const
    {
        Input input(m_string, m_index);
        input.m_epsilon = true;
        return input;
    }
    
    char get_char() const
    {
        assert(m_index < m_string.size());
        return m_string[m_index];
    }

    Anchor get_anchor() const;

private:
    const std::string &m_string;
    uint m_index;
    bool m_epsilon;
};

struct Trigger
{
    Trigger(const std::string &str, Anchor anchor)
        : m_string(str), m_anchor(anchor) 
    {
        std::sort(m_string.begin(), m_string.end());
    }

    bool is_epsilon() const
    {
        return m_string.empty();
    }
    
    bool match_only_anchor(const Input &input) const;
    bool match(const Input &input) const;

    std::string m_string; // Must be sorted because we call binary_search
    Anchor m_anchor;
};

struct Transition
{
    Transition(uint curr, uint next, const Trigger &trigger)
        : m_curr(curr), m_next(next), m_trigger(trigger) 
    {
    }

    uint m_curr;
    uint m_next;
    Trigger m_trigger;
};

class Nfa
{
public:
    Nfa();
    
    uint get_start_state() const;
    bool get_next_states(uint curr, const Input &input, std::vector<uint> &next) const;
    bool is_accept(uint u) const;
    bool get_transitions(uint curr, std::vector<Transition> &trans) const;

    uint add_state();
    void add_transition(uint curr, uint next, const Trigger &trigger);
    void add_epsilon_transition(uint curr, uint next);
    void set_accept(uint u);
    void finalize();
    void clear();

    bool has_accept(const std::vector<uint> &states) const;
    bool remove_accept(std::vector<uint> &states) const;

private:
    bool find_match_transitions(uint curr, uint &start, uint &end) const;

    static bool less_transition(const Transition &left, const Transition &right);
    
private:
    uint m_curr;
    bool m_dirty;
    std::vector<Transition> m_transitions;
    std::vector<uint> m_accepts;
};

struct MatchResult
{
    const std::string *m_original;
    uint m_start;
    uint m_end;
};

class NfaMatcher
{
public:
    static bool match(const Nfa &nfa, const std::string &str, MatchResult &mr);
};

class NfaBuilder
{
public:
    static bool build(const std::string &str, Nfa &nfa);

private:
    static char escape(const std::string &str, uint &i);
    static bool parse_char_set(const std::string &str, uint &i, std::string &chars);
};

}
